Homework 2, Due Date: Nov. 11th, 7 PM, using SUBMIT
command.
Assigned: 30 Oct. 2003
Note: Submit a PDF/PS file of a TYPEWRITTEN (or Wordprocessor-based) or
scanned handwritten (should be legible to be eligible for grading) homework. If
hand-written document is not scanning well, it can be turned in class PRIOR to
above deadline.
The command to run is specific to your section:
- submit cs421_0101
hwk2 FILE_NAME for Section 0101
- submit
cs421_0201 hwk2 FILE_NAME for Section 0201
- submit
cs421_0301 hwk2 FILE_NAME for Section 0301
Answer the following
questions. Note that the problem numbers refer to OSC, 6th Ed, XP Update
Edition.
- Problem
7.8: The Sleeping-Barber Problem. A barbershop consists of a waiting room
with n chairs and the barber room containing the barber chair. If there
are no customers to be served, the barber goes to sleep. If a customer
enters the barbershop and all chairs are occupied, then the customer
leaves the shop. If the barber is busy but chairs are available, then the
customer sits in one of the free chairs. If the
barber is asleep, the customer wakes up the barber. Write a program to
coordinate the barber and the
customers.
- Problem
7.15. A file is to be shared among different processes, each of
which has a unique number. The file can be accessed
simultaneously by several processes, subject to the following
constraint: The sum of all unique numbers associated with all the
processes currently accessing the file must be less than n. Write
a monitor to coordinate access to the file.
- Problem
7.18. Why does Solaris implement multiple locking mechanisms?
Under what circumstances does it use spinlocks, semaphores, adaptive
mutexes, conditional variables, and readers-writers locks? Why does it
use each mechanism? What is the purpose of
turnstiles
- Problem
8.4 Consider the traffic
deadlock depicted in Figure 8.8 (please see the book for this Picture).
- Show
that the four necessary conditions for deadlock indeed hold in this example
- State
a simple rule that will avoid deadlocks in this system.
- Problem
8.6 In a real computer system, neither the resources available nor the
demands of processes for resources are consistent over long periods
(months). Resources break or are replaced, new processes come and go, new
resources are bought and added to the system. If deadlock is controlled by
the banker's algorithm, which of the following changes can be made safely
(without introducing the possibility of deadlock), and under what
circumstances?
- Increase Available (new resources added)
- Decrease Available (resource permanently removed from system)
- Increase Max for one process (the process needs more
resources than allowed, it may want more)
- Decrease Max for one process (the process decides it does
not need that many resources)
- Increase the number of processes.
- Decrease the number of processes.
- Problem
8.9: Consider a system consisting of m resources of the same type, being
shared by n processes. Resources can be requested and released by
processes only one at a time. Show that the system is deadlock-free if the
following two conditions hold:
- The
maximum need of each process is between 1 and m resources.
- The
sum of all maximum needs is less than m+n.
- Problem
8.13 Consider the following snapshot of a system:
Allocation
Max
Available
----------------
-------------------
----------------
A B C D A B C D A
B C D
P0 0 0 1
2
0 0 1 2 1 5 2
0
P1 1 0 0 0
1 7 5 0
P2 1 3 5 4
2 3
5 6
P3 0 6 3 2
0 6 5 2
P4 0 0 1
4
0 6 5 6
Answer the following
questions using the banker’s algorithm:
a: What is the content of the matrix Need?
b: Is the system in a safe state?
c:If a request from process P1 arrives for (0,4,2,0), can the
request be granted immediately?